package gold.gold04;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * binarySearch, 有序的数列, 非常好
 * Collections和Arrays都有binarySearch方法, 使用都是Collections.binarySearch(List, key), 这样的。
 */
public class S1010数字流的秩 {
}
class StreamRank {
    /**
     * 40, 好诶。虽然不快, 但是写得不错。
     * 使用一个有序list来插入, 然后返回binarySearch, 注意binarySearch返回的是负数的情况
     *
     * 总结一下Collections.binarySearch(), 如果找不到值的话, 会返回 - (low + 1), 值本身比low大, 所以返回值posi
     * 那么 - posi - 1得到的是小于x的最大的值
     * 但是因为是返回二分查找的第一个与x相等的值, 所以如果找到的话, 他的左右仍然有可能是与x相等的值, 所以需要根据实际情况做一些左右移动的处理。
     */
    private List<Integer> numsRecord;
    public StreamRank() {
        numsRecord = new ArrayList<>();
    }

    public void track(int x) {
        // 在插入的时候就保持他是一个有序状态。这样操作分数从40->52, 比插一次排序一次好
        int insertPosi = Collections.binarySearch(numsRecord, x);
        insertPosi = insertPosi < 0? - insertPosi - 1: insertPosi;
        numsRecord.add(insertPosi, x); // 实现了我想要的有序数组, 并且没有使用排序, 插入的复杂度是logn。

        // numsRecord.add(x);
        // numsRecord.sort(null); // 这个步骤可以在track里, 也可以在getRankOfNumber里

    }

    public int getRankOfNumber(int x) {
        int posi = Collections.binarySearch(numsRecord, x);
        // 注意这个indexOf, 如果没有这么个值, 返回的是-1(这个特性很重要, 让这种题目的场合根本就不能用了); 并且indexOf是逐个查找的。
        // int posiIndex = numsRecord.indexOf()
        if(posi < 0) return - posi - 1;
        while(posi >= 0 && posi < numsRecord.size() && numsRecord.get(posi) == x){
            posi ++; // 找到第一个 >= x 的位置
        }
        return posi;
    }
}
